//
//  BinaryManager.swift
//  BinaryTree
//
//  Created by 郭红旗 on 2022/1/8.
//

import UIKit

class BinaryRBManager<T:Equatable>: BinaryManager<T>  {
    override func afterAdd(node: TreeNode<T>) {
        <#code#>
    }
}

class BinaryAVLAManager<T:Equatable>: BinaryManager<T> {
    override func afterAdd(node: TreeNode<T>) {
        super.afterAdd(node: node)
        var parent:TreeNode<T>? = node
        while parent != nil {
            if parent!.isBalance {
                updateHight(node: parent!)
            }else{
                balance(node: parent!)
                break
            }
            parent = parent!.parent
        }
    }
    override func afterRemove(node: TreeNode<T>?) {
        super.afterRemove(node: node)
        var parent:TreeNode<T>? = node
        while parent != nil {
            if parent!.isBalance {
                updateHight(node: parent!)
            }else{
                balance(node: parent!)
            }
            parent = parent!.parent
        }
    }
    
    override func updateHight(node:TreeNode<T>?) {
        super.updateHight(node: node)
        node?.updateHight()
    }
    func balance(node:TreeNode<T>) {
        let grand = node
        guard let parent = grand.trailChild(),
        let child = parent.trailChild() else {
            return
        }
        
        if parent.isLeft { // L
            if child.isLeft { // LL
                rotateRight(node: grand)
            }else{ // LR
                rotateLeft(node: parent)
                rotateRight(node: grand)
            }
        }else{// R
            if child.isRight { // RR
                rotateLeft(node: grand)
            }else{ // RL
                rotateRight(node: parent)
                rotateLeft(node: grand)
            }
        }
    }
    
    
}


class BinaryManager<T:Equatable> {
    typealias comparatorClosure = (_ e1:T,_ e2:T) -> Int
    private var comparator:comparatorClosure
    var root:TreeNode<T>?
    init(comparator:@escaping comparatorClosure) {
        self.comparator = comparator
    }
    func printFunc() {
        print(root!.asString)
    }
    // MARK: -添加
    func addValue(value:T) {
        root = add(withRecursion: value, node: root)
    }
    func add(withRecursion value:T,node:TreeNode<T>?) -> TreeNode<T>{
        guard let tree = node else {
            return TreeNode.init(value: value, parent: nil)
        }
        let result = comparator(value,tree.element!)

        if result < 0 {
            tree.left = add(withRecursion: value, node: tree.left)
        }else{
            tree.right = add(withRecursion: value, node: tree.right)
        }
        return tree
    }
    func add(value:T) {
        guard let node = root else {
            root = TreeNode.init(value: value, parent: nil)
            afterAdd(node: root!)
            return
        }
        
        var tree:TreeNode<T>? = node
        var result:Int = 0
        var last = node
        while tree != nil {
            result = comparator(value,tree!.element!)
            last = tree!
            if result < 0 {
                tree = tree!.left
            }else{
                tree = tree!.right
            }
        }
        let new = TreeNode.init(value: value, parent: last)
        if result < 0 {
            last.left = new
        }else{
            last.right = new
        }
        afterAdd(node: new)
        
    }
    func afterAdd(node:TreeNode<T>) {}
    func updateHight(node:TreeNode<T>?) {}

    // MARK: - 移除
    func afterRemove(node:TreeNode<T>?) {
        
    }
    func remove(value:T) {
        guard var node = node(withValue: value) else {
            return
        }
        if node.hasTwoChild {
            let precursor = precursorNode(node: node)
            node.element = precursor.element
            node = precursor
        }
        if node.leafNode {
            let replace = node.left == nil ? node.right! : node.left!
            if node.isLeft {
                node.parent?.left = replace
            }else{
                node.parent?.right = replace
            }
            afterRemove(node: replace)
        }else{
            if node.isLeft {
                node.parent?.left = nil
            }else{
                node.parent?.right = nil
            }
            afterRemove(node: node)
        }
    }
    
    
    func rotateLeft(node:TreeNode<T>) {
        let grand = node
        let parent = grand.right
        let child = parent?.left
        
        grand.right = child
        parent?.left = grand
        parent?.parent = grand.parent
        
        if grand.isLeft {
            grand.parent?.left = parent
        }else if grand.isRight{
            grand.parent?.right = parent
        }else{
            root = parent
        }
        child?.parent = grand
        grand.parent = parent
        updateHight(node: grand)
        updateHight(node: parent)
    }
    func rotateRight(node:TreeNode<T>) {
        let grand = node
        let parent = grand.left
        let child = parent?.right
        
        grand.left = child
        parent?.right = grand
        parent?.parent = grand.parent
        
        if grand.isRight {
            grand.parent?.right = parent
        }else if grand.isLeft{
            grand.parent?.left = parent
        }else{
            root = parent
        }
        child?.parent = grand
        grand.parent = parent
        updateHight(node: grand)
        updateHight(node: parent)
    }
    func node(withValue value:T) -> TreeNode<T>? {
        var node = root
        while node != nil {
            let result = comparator(value,node!.element!)
            if result < 0 {
                node = node?.left
            }else if result > 0{
                node = node?.right
            }else{
                break
            }
        }
        return node
    }
    func precursorNode(node:TreeNode<T>) -> TreeNode<T> {
        var tree = node.left
        var result = tree
        while tree != nil {
            result = tree
            tree = tree?.right
        }
        return result!
    }
}


class TreeNode<U:Equatable> {
    var left:TreeNode?
    var right:TreeNode?
    var parent:TreeNode?
    var element:U?
    var hight:Int = 0
    var asString:String {return treeString(self){("\($0.element!)",$0.left,$0.right)}}
    var isBalance:Bool{
        get{
            var leftHight = 0
            var rightHight = 0
            leftHight = left?.hight ?? 0
            rightHight = right?.hight ?? 0
            return abs((leftHight - rightHight)) < 2
        }
    }
    var isLeft:Bool{
        get{
            if self.element == parent?.left?.element {
                return true
            }
            return false
        }
    }
    var isRight:Bool{
        get{
            if self.element == parent?.right?.element {
                return true
            }
            return false
        }
    }
    var hasTwoChild:Bool{
        get{
            if left != nil && right != nil {
                return true
            }
            return false
        }
    }
    var leafNode:Bool{
        get{
            if left != nil || right != nil {
                return true
            }
            return false
        }
    }
    init(value:U,parent:TreeNode?) {
        element = value
        self.parent = parent
    }
    func updateHight(){
        var leftHight = 0
        var rightHight = 0
        leftHight = left?.hight ?? 0
        rightHight = right?.hight ?? 0
        if leftHight > rightHight {
            hight = leftHight + 1
        }else{
            hight = rightHight + 1
        }
    }
    func trailChild() -> TreeNode<U>? {
        var leftHight = 0
        var rightHight = 0
        leftHight = left?.hight ?? 0
        rightHight = right?.hight ?? 0
        if leftHight > rightHight {
            return left
        }else if rightHight > leftHight{
            return right
        }else{
            if isLeft {
                return left
            }else{
                return right
            }
        }
    }

}
